/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM27 按之字形顺序打印二叉树
 * <a href="https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0?tpId=295&tqId=23454&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj">...</a>
 * User: DELL
 * Data: 2022-11-30
 * Time: 23:07
 */
import java.util.*;


class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer>>();
        //处理空树
        if (pRoot == null) {
            return res;
        }
        //用队列存储每次遍历的结点，层次遍历
        Queue<TreeNode> tmp = new LinkedList<>();
        tmp.offer(pRoot);
        boolean flag = true;  //记录当前是否需要反转
        while (!tmp.isEmpty()) {
            //记录当前层遍历的val
            ArrayList<Integer> row = new ArrayList<>();
            int n = tmp.size();
            //标志改变
            flag = !flag;
            for (int i = 0; i < n; i++) {
                TreeNode cur = tmp.poll();
                if ( cur.left != null) {
                    tmp.offer(cur.left);
                }
                if ( cur.right != null) {
                    tmp.offer(cur.right);
                }
                row.add(cur.val);
            }
            if (flag) {
                Collections.reverse(row);
            }
            res.add(row);
        }
        return res;
    }
}

